package tree

import (
	"container/list"
)

func RecursivePreOrderTravel(root *BinaryTreeNode) {
	if nil == root {
		return
	}

	root.PrintVal()
	RecursivePreOrderTravel(root.Left)
	RecursivePreOrderTravel(root.Right)
}

func Loop1PreOrderTravel(root *BinaryTreeNode) {
	s := list.New()
	for curr := root; nil != curr || s.Len() > 0; {
		for nil != curr {
			curr.PrintVal()
			s.PushBack(curr)
			curr = curr.Left
		}

		top := s.Back()
		curr, _ = top.Value.(*BinaryTreeNode)
		s.Remove(top)
		curr = curr.Right
	}
}

func Loop2PreOrderTravel(root *BinaryTreeNode) {
	s := list.New()
	s.PushBack(root)

	for s.Len() > 0 {
		top := s.Back()
		s.Remove(top)

		var curr *BinaryTreeNode
		if curr, _ = top.Value.(*BinaryTreeNode); nil == curr {
			continue
		}

		top.Value.(*BinaryTreeNode).PrintVal()
		s.PushBack(curr.Right)
		s.PushBack(curr.Left)
	}

}

func RecursiveMidOrderTravel(root *BinaryTreeNode) {
	if nil == root {
		return
	}

	RecursiveMidOrderTravel(root.Left)
	root.PrintVal()
	RecursiveMidOrderTravel(root.Right)
}

func Loop1MidOrderTravel(root *BinaryTreeNode) {
	s := list.New()

	for curr := root; nil != curr || s.Len() > 0; {
		for nil != curr {
			s.PushBack(curr)
			curr = curr.Left
		}

		top := s.Back()
		s.Remove(top)

		curr, _ = top.Value.(*BinaryTreeNode)
		curr.PrintVal()

		curr = curr.Right
	}
}

func Loop2MidOrderTravel(root *BinaryTreeNode) {

}

func RecursivePostOrderTravel(root *BinaryTreeNode) {
	if nil == root {
		return
	}

	RecursivePostOrderTravel(root.Left)
	RecursivePostOrderTravel(root.Right)
	root.PrintVal()
}

func Loop1PostOrderTravel(root *BinaryTreeNode) {
	s := list.New()
	var curr, last *BinaryTreeNode

	for curr = root; nil != curr || s.Len() > 0; {
		for nil != curr {
			s.PushBack(curr)
			curr = curr.Left
		}

		top, _ := s.Back().Value.(*BinaryTreeNode)
		if nil == top.Right || last == top.Right { // 退栈节点top为叶子节点 || 退栈节点top的右孩子已访问过
			top.PrintVal()
			last = top
			s.Remove(s.Back())
		} else {
			curr = top.Right
		}
	}
}

func Loop2PostOrderTravel(root *BinaryTreeNode) {

}
